package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode060 
* @author      : ganwei 
* @date        : 2020年5月8日 
* @Description : 60. 第k个排列 
*/
public class Leetcode0060 {
    
	List<String> result = new ArrayList<>();
	/**
	 * -解题思路，回溯打法 361589472
	 */
	public String getPermutation(int n, int k) {
		backtrack(n, k, new StringBuilder(),new boolean[n+1]);
    	return result.get(k-1);
    }
    
    public boolean backtrack(int n, int k,StringBuilder sb, boolean[] isVisited) {
    	if(sb.length() == n) {
    		result.add(sb.toString());
    		if(result.size() == k) {
    			return true;
    		}else {
    			return false;
    		}
    	}
    	for(int i = 1; i <= n; i++) {
    		if(isVisited[i]) {
    			continue;
    		}
    		
    		sb.append(i);
    		isVisited[i] = true;
    		
    		if(backtrack(n,k,sb,isVisited)) {
    			return true;
    		}
    		
    		sb.deleteCharAt(sb.length()-1);
    		isVisited[i] = false;
    	}
    	return false;
    }
    
	/**
	 * -解题思路，回溯算法复杂度太高
	 */
	public String getPermutation_1(int n, int k) {
		/*
		 * 初始化数列
		 */
        List<Integer> num = new ArrayList<>();
        for (int i = 1; i <= n; i++) num.add(i);
        
        int[] factorial = new int[n];
        factorial[0] = 1;
        /*
         * 初始化排列个数 数组
         */
        for (int i = 1; i < n; i++) factorial[i] = i * factorial[i-1];
        
        n--;
        StringBuilder res = new StringBuilder();
        while (n >= 0){
            int t = factorial[n];
            int loc = (int) (Math.ceil((double) k / (double) t)) - 1;
            if (loc == -1) loc = num.size() - 1;
            
            res.append(num.get(loc));
            num.remove(loc);
            k %= t;
            n--;
        }
        return res.toString();

    }
    
    public static void main(String[] args) {
    	Leetcode0060 l060 = new Leetcode0060();
    	System.out.println(l060.getPermutation_1(9,1));
    }
}
